package arithmetic;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Objects;

/**
 * 三一个集合，里面三个数相加为零的个数
 * <p>
 * 思想：三个数和为零，那么这个数组肯定有正数也有负数，如果暴力匹配，就是三层循环，时间复杂度是o(n^3),所以这样的
 * 方式肯定不行。既然集合有正有负，那么就将他们排序，然后从小到大，收尾相加向中间聚拢，则获取为零的结果会多一些，同时
 * 效率也会高。
 * 基于上面的分析，设计算法：
 * 先将数组排序，i指向数组的开始，j指向数组的下一位，k指向数组的最后。
 * 如果： arr[i]+arr[j]+arr[k]=0   ,j++   k--;
 * 如果： arr[i]+arr[j]+arr[k]>0   , k--;
 * 如果： arr[i]+arr[j]+arr[k]<0   , j++;
 * while 循环满足条件：j<k
 */
public class FindTriplets {

    public static void main(String[] args) {
        int arr[] = {-1, 2, 3, 4, -5, 0, -4, 2, 4, 2, 5, 1, 5, -23, -9, 5, 2, -8, 10, 7, -15, 6, 13, 6, -9, -8, -78, -70, 70, 4, 4, 5, -5};
        int triplets1 = FindTriplets.findTriplets1(arr);
       // System.out.println(triplets1);
    }

    /**
     * 这个时间复杂度是n*n
     *
     * @param arr
     * @return
     */
    public static int findTriplets(int[] arr) {

        int nums = 0;
        Arrays.sort(arr);
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                if (arr[i] + arr[j] + arr[k] == 0) {
                    System.out.println(arr[i] + " " + arr[j] + " " + arr[k]);
                    nums++;
                    j++;
                    k--;

                } else if (arr[i] + arr[j] + arr[k] > 0) {
                    k--;
                } else {
                    j++;
                }

            }
        }
        return nums;

    }

    /**
     * 另一种方法： 三个数和等于0  就是A+B+C=0  既：A=-(A+B) , 在数组中找到 和 -(arr[i]+arr[j])匹配的值且不等于arr[i]也不等于arr[j],
     * 这样就将题目变为：在数组中查找某个值是否存在，可以使用二分法查找。
     *
     * 这里为什么要大于j,原因是希望得到的数字都是从小到大排序，避免重复。
     *
     */
    public static int findTriplets1(int[] arr) {
        Arrays.sort(arr);
        HashSet<SameInteger>  hashSet=new HashSet<>();
        int k = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                int nums = arr[i] + arr[j];
                if (-nums>arr[i]&&nums != arr[i] && nums != arr[j] && Arrays.binarySearch(arr, -nums) > 1) {
                    hashSet.add(new SameInteger(arr[i],arr[j],-nums));
                    System.out.println(arr[i] + " " + arr[j] + " " + -nums);
                    k++;
                }

            }
        }
        System.out.println(hashSet);
        System.out.println(hashSet.size());
        return k;
    }

    static class  SameInteger {
        Integer a;
        Integer b;
        Integer c;

        public SameInteger(Integer a, Integer b, Integer c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        public Integer getA() {
            return a;
        }

        public void setA(Integer a) {
            this.a = a;
        }

        public Integer getB() {
            return b;
        }

        public void setB(Integer b) {
            this.b = b;
        }

        public Integer getC() {
            return c;
        }

        public void setC(Integer c) {
            this.c = c;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            SameInteger that = (SameInteger) o;
            return Objects.equals(a, that.a) && Objects.equals(b, that.b) && Objects.equals(c, that.c);
        }

        @Override
        public int hashCode() {
            return Objects.hash(a, b, c);
        }

        @Override
        public String toString() {
            return a + " " + b + " " + c + "|";
        }
    }

}
